package niuke;

import java.util.*;

public class LRU {
    //HashMap+自定义双向链表
    private Map<Integer, Node> map = new HashMap<>();
    private Node head = new Node(-1, -1);
    private Node tail = new Node(-1, -1);
    private int k; //链表的最大长度

    public int[] LRU(int[][] operators, int k) {
        this.k = k;
        head.next = tail;
        tail.prev = head;
        //
        int len = (int) Arrays.stream(operators).filter(x -> x[0] == 2).count();
        int[] res = new int[len];
        for (int i = 0, j = 0; i < operators.length; i++) {
            // 1 添加
            if (operators[i][0] == 1) {
                set(operators[i][1], operators[i][2]);
            } else {
                // 2 查询
                res[j++] = get(operators[i][1]);
            }
        }
        return res;
    }

    private void set(int key, int val) {
        //若key存在 直接更新值
        if (get(key) > -1) {
            map.get(k).val = val;
        } else {
            if (map.size() == k) {
                //移除掉最后一个节点 再添加进去
                int rk = tail.prev.key;
                tail.prev.prev.next = tail;
                tail.prev = tail.prev.prev;
                map.remove(rk);
            }
            Node node = new Node(key, val);
            map.put(key, node);
            //移动到头结点上去
            moveToHead(node);
        }
    }

    private int get(int key) {
        //若map中有 移动到头结点上去
        if (map.containsKey(key)) {
            Node node = map.get(key);
            //断开node节点
            node.prev.next = node.next;
            node.next.prev = node.prev;
            //移动到头节点去
            moveToHead(node);
            //返回node值
            return node.val;
        }
        return -1;
    }

    //将当前节点移动到头结点去
    private void moveToHead(Node node) {
        //head是一个虚拟节点-1 双向链表 连接四条边
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }

    //双向链表
    static class Node {
        int key, val;
        Node prev, next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
}